# LeetCode 43、字符串相乘
# 一、题目描述
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
**注意：**不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
提示：
1 <= num1.length, num2.length <= 200num1和num2只能由数字组成。num1和num2都不包含任何前导零，除了数字0本身。
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：wzb_3377
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 字符串相乘（LeetCode 43）：https://leetcode.cn/problems/multiply-strings/submissions/
class Solution {
public String multiply(String num1, String num2) {
// 边界处理，任何数和 0 相乘都为 0
if (num1.equals("0") || num2.equals("0")) {
// 直接返回 0
return "0";
}
// 获取字符串 num1 的长度
int m = num1.length() ;
// 获取字符串 num2 的长度
int n = num2.length();
// 基于这两个长度可以构造一个长度为 m + n 的数组
// 因为假设 m = 2 ，最大数是 99
// n = 3 ，最大数是 999
// 两者相乘的结果 98901 长度为 5
int[] ansArr = new int[m + n];
// 从后向前依次访问 num1 中的元素
for (int i = m - 1; i >= 0; i--) {
// '0' 的 ASCII 码是 48 ，'1' 的是 49
// 获取数字，相当于字符串转整数操作
int x = num1.charAt(i) - 48 ;
// 从后向前依次访问 num2 中的元素
for (int j = n - 1; j >= 0; j--) {
// '0' 的 ASCII 码是 48 ，'1' 的是 49
// 获取数字，相当于字符串转整数操作
int y = num2.charAt(j) - 48;
// 把 x 和 y 相乘的结果存放到 i + j + 1 位
// 比如一开始 i = m - 1 、j = n - 1
// 那么就存放到 m - 1 + n - 1 + 1 = m + n - 1
// 数组的索引是从 0 开始 ，即此时存放到了最后一位
// 并且由于 x 和 y 必然都是个位数，相乘的结果最多只能是两位数
ansArr[ i + j + 1 ] += x * y;
}
}
// 接下来，需要把 ansArr 的每一位都拿出来查看一下
// 使得每一个都只存放一位数字，多余的传递给上一层
for (int k = m + n - 1; k > 0; k--) {
// 上一位的数字需要累加当前这一位的十位数
// 比如 ansArr[k] = 24 ， ansArr[k - 1] = 68
// 那么 ansArr[k - 1] 需要加上 2 ，变成了 70
ansArr[k - 1] += ansArr[k] / 10;
// 然后 ansArr[k] 就更新为它的个位数
ansArr[k] %= 10;
}
// 最后，开始把数组转换为字符串的形式
StringBuffer ans = new StringBuffer();
// 从最高位开始接收
// 此时，需要判断一下 ansArr[0] 是否为 0 ， 如果为 0 ，那么就抛弃这一位，从下一位在开始接收
int index = ansArr[0] == 0 ? 1 : 0;
// 不断的去填充字符串
while (index < m + n) {
// 一位一位去接收
ans.append(ansArr[index]);
// 再去填充下一位
index++;
}
// 最后返回结果
return ans.toString();
}
}
# 2、C++ 代码
class Solution {
public:
string multiply(string num1, string num2) {
// 边界处理，任何数和 0 相乘都为 0
if (num1 == "0" || num2 == "0") {
// 直接返回 0
return "0";
}
// 获取字符串 num1 的长度
int m = num1.size() ;
// 获取字符串 num2 的长度
int n = num2.size();
// 基于这两个长度可以构造一个长度为 m + n 的数组
// 因为假设 m = 2 ，最大数是 99
// n = 3 ，最大数是 999
// 两者相乘的结果 98901 长度为 5
auto ansArr = vector<int>(m + n);
// 从后向前依次访问 num1 中的元素
for (int i = m - 1; i >= 0; i--) {
// '0' 的 ASCII 码是 48 ，'1' 的是 49
// 获取数字，相当于字符串转整数操作
int x = num1.at(i) - '0' ;
// 从后向前依次访问 num2 中的元素
for (int j = n - 1; j >= 0; j--) {
// '0' 的 ASCII 码是 48 ，'1' 的是 49
// 获取数字，相当于字符串转整数操作
int y = num2.at(j) - '0';
// 把 x 和 y 相乘的结果存放到 i + j + 1 位
// 比如一开始 i = m - 1 、j = n - 1
// 那么就存放到 m - 1 + n - 1 + 1 = m + n - 1
// 数组的索引是从 0 开始 ，即此时存放到了最后一位
// 并且由于 x 和 y 必然都是个位数，相乘的结果最多只能是两位数
ansArr[ i + j + 1 ] += x * y;
}
}
// 接下来，需要把 ansArr 的每一位都拿出来查看一下
// 使得每一个都只存放一位数字，多余的传递给上一层
for (int k = m + n - 1; k > 0; k--) {
// 上一位的数字需要累加当前这一位的十位数
// 比如 ansArr[k] = 24 ， ansArr[k - 1] = 68
// 那么 ansArr[k - 1] 需要加上 2 ，变成了 70
ansArr[k - 1] += ansArr[k] / 10;
// 然后 ansArr[k] 就更新为它的个位数
ansArr[k] %= 10;
}
// 最后，开始把数组转换为字符串的形式
string ans;
// 从最高位开始接收
// 此时，需要判断一下 ansArr[0] 是否为 0 ， 如果为 0 ，那么就抛弃这一位，从下一位在开始接收
int index = ansArr[0] == 0 ? 1 : 0;
// 不断的去填充字符串
while (index < m + n) {
// 一位一位去接收
ans.push_back(ansArr[index]);
// 再去填充下一位
index++;
}
// 转换为数字的形式
for (auto &c: ans) {
c += '0';
}
// 最后返回结果
return ans;
}
};
# 3、Python 代码
class Solution:
def multiply(self, num1: str, num2: str) -> str:
# 边界处理，任何数和 0 相乘都为 0
if num1 == "0" or num2 == "0":
# 直接返回 0
return "0"
# 获取字符串 num1 的长度
m = len(num1)
# 获取字符串 num2 的长度
n = len(num2)
# 基于这两个长度可以构造一个长度为 m + n 的数组
# 因为假设 m = 2 ，最大数是 99
# n = 3 ，最大数是 999
# 两者相乘的结果 98901 长度为 5
ansArr = [0] * (m + n)
# 从后向前依次访问 num1 中的元素
for i in range(m - 1, -1, -1):
# '0' 的 ASCII 码是 48 ，'1' 的是 49
# 获取数字，相当于字符串转整数操作
x = int(num1[i])
# 从后向前依次访问 num2 中的元素
for j in range(n - 1, -1, -1):
# '0' 的 ASCII 码是 48 ，'1' 的是 49
# 获取数字，相当于字符串转整数操作
y = int(num2[j])
# 把 x 和 y 相乘的结果存放到 i + j + 1 位
# 比如一开始 i = m - 1 、j = n - 1
# 那么就存放到 m - 1 + n - 1 + 1 = m + n - 1
# 数组的索引是从 0 开始 ，即此时存放到了最后一位
# 并且由于 x 和 y 必然都是个位数，相乘的结果最多只能是两位数
ansArr[ i + j + 1 ] += x * y
# 接下来，需要把 ansArr 的每一位都拿出来查看一下
# 使得每一个都只存放一位数字，多余的传递给上一层
for k in range(m + n - 1, 0, -1):
# 上一位的数字需要累加当前这一位的十位数
# 比如 ansArr[k] = 24 ， ansArr[k - 1] = 68
# 那么 ansArr[k - 1] 需要加上 2 ，变成了 70
ansArr[k - 1] += ansArr[k] // 10
# 然后 ansArr[k] 就更新为它的个位数
ansArr[k] %= 10
# 最后，开始把数组转换为字符串的形式
# 从最高位开始接收
# 此时，需要判断一下 ansArr[0] 是否为 0 ， 如果为 0 ，那么就抛弃这一位，从下一位在开始接收
index = 1 if ansArr[0] == 0 else 0
# 不断的去填充字符串
ans = "".join(str(x) for x in ansArr[index:])
# 最后返回结果
return ans